package leetcode_core.leetcode_1;

public class DeleteNode {
        public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
        }
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null){
            return root;
        }
        if(root.val == key){//遍历查找得到了val为key的节点,进行删除
            //情况1:这个节点没有子节点
            if(root.left == null && root.right == null){
                return null;
            }
            //情况2:这个节点只有一个子节点
            if(root.left == null){//这里省略了root.right != null,因为前一个分支条件语句覆盖掉了
                //这时候只需要把右子树给接替上来就好了
                return root.right;
            }
            if(root.right == null){
                return root.left;
            }
            //情况3,左右子树都不是空,这时候我们需要找到一个节点,这个节点可以是左子树最大的节点,可以是右子树最小的节点
            TreeNode max = getMax(root.left);//这里找的是右子树的最小节点
            //然后进行删除,这里根据BST的数据结构特点来进行操作,注意,无论是最大的节点还是最小的节点,我们发现它都是叶子节点,那么我们剩下就是要删除叶子节点嘛
            //我们就是在编写删除操作,于是删除这个事情我们把它交给递归就好了
            root.val = max.val;
            root.left = deleteNode(root.left,root.val);
        }

        //否则的话就继续遍历,这里的话key比root的值要大,那么就要遍历值更大的右子树
        else if(root.val < key){
            root.right = deleteNode(root.right,key);
        }else if(root.val > key){
            root.left = deleteNode(root.left,key);
        }
        return root;
    }

    private TreeNode getMin(TreeNode root){
        //向左遍历
        while(root.left !=null){
            root = root.left;
        }
        return root;
    }

    private TreeNode getMax(TreeNode root){
        //向左遍历
        while(root.right !=null){
            root = root.right;
        }
        return root;
    }

}
